//题目:
// 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
// 树的 最大宽度 是所有层中最大的 宽度 。
// 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。
// 将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的null节点，这些null节点也计入长度。
// 题目数据保证答案将会在  32 位 带符号整数范围内。
#include<iostream>
#include<queue>
#include<vector>

using namespace std;
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
//代码:
// class Solution 
// {
// public:
//     int widthOfBinaryTree(TreeNode* root) 
//     {
//         //内存超出...
//         int ret=1;
//         queue<TreeNode*> q;
//         if(root!=nullptr)q.push(root);
//         while(!q.empty())
//         {
//             int size=q.size();
//             //每层结点都在此遍历
//             int left=-1,right=-1;
//             for(int i=0;i<size;i++)
//             {
//                 TreeNode* node=q.front();
//                 q.pop();
//                 if(node)
//                 {
//                     q.push(node->left);
//                     q.push(node->right);
//                     //标记左右边界
//                     if(left==-1)left=i;
//                     else right=i;
//                     //更新
//                     if(left!=-1 && right!=-1) ret=max(ret,right-left+1);
//                 }
//                 else
//                 {
//                     q.push(nullptr);
//                     q.push(nullptr);
//                 }
//             }
//             if(left==-1 && right==-1)break;//说明此时该层一个结点都没有
//         }
//         return ret;
//     }
// };

class Solution 
{
public:
    int widthOfBinaryTree(TreeNode* root) 
    {
        unsigned int ret=0;
        //思路：将二叉树看成是数组存储结构，每个父节点和其子节点的关系,左子节点:child=2*parent
        queue<pair<unsigned int,TreeNode*>> q;//key是数组下标，value是树节点指针
        if(root!=nullptr)q.push(make_pair(1,root));
        while(!q.empty())
        {
            int size=q.size();
            unsigned left=0,right=0;
            for(int i=0;i<size;i++)
            {
                pair<unsigned int,TreeNode*> pir=q.front();
                q.pop();
                if(pir.second->left)q.push(make_pair(pir.first*2,pir.second->left));
                if(pir.second->right)q.push(make_pair(pir.first*2+1,pir.second->right));

                //标记最左边和最右边的结点
                if(i==0)left=pir.first;
                if(i==size-1)right=pir.first;
            }
            ret=max(ret,right-left+1);
        }
        return ret;
    }
};
